1. Field of the Invention
Embodiments of the present invention generally relate to techniques for routing data in a network. More specifically, embodiments of the present invention relate to a method for performing routing in a multi-hop network based on a retransmission-time-based link metric.
2. Related Art
In a multi-hop routing network, a path or a route (used interchangeably throughout) between a source node and a destination node is comprised of a set of hops or links. Here a hop or a link (used interchangeably throughout) is defined as a logically direct communication path (either wired or wireless) between a pair of adjacent nodes. A respective link in the multi-hop routing network is typically associated with one or more link metrics, which can be used to compute a cost associated with using the link for data transmission. A path cost can then be computed as a sum of the link cost on each link comprising the path. Next, a multi-hop routing protocol is used to select a path between a source node and a destination node based on the associated path cost to facilitate efficient routing through the multi-hop wireless network.
For example, one routing protocol seeks a route with a minimum hop count, or a “min-hop.” In this protocol, the link metric used by the protocol simply assumes that each link has a cost of “1” and the path cost equals the number of hops within the route. Another routing protocol searches for a route with the minimum latency or delay. In this protocol, the link metric used by the protocol is the link traversal time, and a path cost is the sum of each link traversal time over the path. Sometimes, a routing protocol may consider more than one type of link metric, and seek a path based on a trade-off among multiple link metrics.
Note that the aforementioned minimum delay metric provides a good path-cost estimation in a wired network. This is because a wired network generally exhibits a high success rate in data transmission. Hence, link delays are relatively deterministic and easy to obtain, for example, by measuring a round-trip (RT) time. However, in a time division multiple access (TDMA)-based wireless network, a link delay can be affected by a number of nondeterministic factors which make the link cost difficult to compute. These factors can include queuing delay due to TDMA scheduling, medium access delay for waiting until medium becomes idle to avoid collision, and retransmission delay due to data transmission failures. Consequently, in a TDMA wireless network, the aforementioned link metrics are not sufficient to accurately represent a link cost.